package ParaProfiler;

/**
 * QuickSort.java
 * @author Lars Vogel.
 * @version 0.6
 * @since 17/05/2009
 * Tomado de : http://www.vogella.com/articles/JavaAlgorithmsQuicksort/article.html
 * Recopilado por Oscar Castañeda, Carnet 11086.
 *            Se modifico para funcionar con objetos comparables.
 * Descripción: Realizar un ordenamiento del tipo QuickSort con una lista de objetos comparables.
 */

public class QuickSort  {
	private Comparable[] values;
	private int number;

        /**
         * Realizar un QuickSort con la lista de objetos comparables ingresada como parámetro.
         * @param valuesToSort Lista a ser ordenada.
         * @return Lista ordenada.
         */
	public Comparable[] sort(Comparable[] valuesToSort) {
		//Se revisa que la lista pasada no sea null o vacía.
		if (valuesToSort ==null || valuesToSort.length==0){
			return null;
		}
		this.values = valuesToSort;
		number = values.length;
		quicksort(0, number - 1);
                return values;
	}

        /**
         * Realiza el ordenamiento de un segmento de la lista, limitado por las
         * posiciones low y high.
         * @param low Índice donde inicia la sublista.
         * @param high Índice donde termina la sublista.
         */
	private void quicksort(int low, int high) {
		int i = low, j = high;
		// Se toma el elemento pivote del medio de la lista.
		Comparable pivot = values[low + (high-low)/2];

		// Se divide en dos listas
		while (i <= j) {
                        // Si el actual elemento de la lista del lado izquierdo es más
                        // pequeño que el elemento pivote, entonces, se avanza al siguiente
                        // elemento de la lista hasta hallar uno mayor.
			while (values[i].compareTo(pivot) < 0) {
				i++;
			}
                        // Si el actual elemento de la lista del lado derecho es mayor que el
                        // elemento pivote, entonces se retrocede al siguiente elemento del lado
                        // derecho hasta hallar uno menor.
			while (values[j].compareTo(pivot) > 0) {
				j--;
			}

			// Si se llega acá, se ha encontrado un elemento del lado izquierdo que 
                        // es mayor que el pivote y uno del lado derecho que es menor. Entonces,
                        // se intercambian estos elementos, para dejar a la izquierda del pivote
                        // a todos los menores, y a la derecha, a todos los mayores.
                        // Luego, se incrementa i y decrementa j para continuar con los demás elementos..
			
			if (i <= j) {
				exchange(i, j);
				i++;
				j--;
			}
		}
		// Recursión: Se realizar el procedimiento de nuevo con cada una de
                // las listas creadas al ordenar respecto al pivote anterior.
		if (low < j)
			quicksort(low, j);
		if (i < high)
			quicksort(i, high);
	}

        /**
         * Intercambia dos posicionesdentro de una lista.
         * @param i Posición de uno de los elementos a intercambiar.
         * @param j Posición del otro de los elementos a intercambiar.
         */
	private void exchange(int i, int j) {
		Comparable temp = values[i];
		values[i] = values[j];
		values[j] = temp;
	}
}
